package november.stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @author huangxin
 * @date 2019/11/15-18:02
 */
public class PolangNotation {
    public static void main(String[] args) {
        String expression = "1+(3+5)*6";
        List<String> stringList = toInfixExpressionList(expression);
        List<String> polangNotation = toPolangNotation(stringList);

        int result = calculate(polangNotation);
        System.out.println(result);
    }

    /**
     * 1)初始化两个栈：运算符栈s1和储存中间结果的栈s2；
     * 2)从左至右扫描中缀表达式；
     * 3)遇到操作数时，将其压s2；
     * 4)遇到运算符时，比较其与s1栈顶运算符的优先级：
     * (1)如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
     * (2)否则，若优先级比栈顶运算符的高，也将运算符压入s1；
     * 否则，将s1栈顶的运算符弹出并压入s2到中，再次转到(4-1)与s1新的栈顶运算符相比较
     * 5)遇到括号时：
     * (1) 如果是左括号“(”，则直接压入s1
     * (2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
     * 6)重复步骤2至5，直到表达式的最右边
     * 7)将s1中剩余的运算符依次弹出并压入s2
     * 8)依次弹出s2中的元素并输出，**结果的逆序即为中缀表达式对应的后缀表达式
     *
     * @param
     * @return
     */
    public static List<String> toPolangNotation(List<String> stringList) {
        Stack<String> s1 = new Stack<>();
        Stack<String> s2 = new Stack<>();
        for (String str : stringList) {
            //判断是否为符号
            if (isOpera(str)) {
                while (true) {
                    if (s1.isEmpty() || "(".equals(s1.peek())) {
                        //栈为空,或者栈顶为(,直接入栈
                        s1.push(str);
                        break;
                    } else {
                        //如果当前符号优先级>栈顶运算符,
                        if (priority(str.charAt(0)) > priority(s1.peek().charAt(0))) {
                            s1.push(str);
                            break;
                        } else {
                            //否则将s1栈顶弹出压入s2
                            s2.push(s1.pop());
                        }
                    }
                }
            } else if ("(".equals(str)) {
                //左括号直接入栈
                s1.push(str);
            } else if (")".equals(str)) {
                //右括号依次弹出s1的元素压入s2,直到遇见左括号
                while (true) {
                    if ("(".equals(s1.peek())) {
                        s1.pop();
                        break;
                    } else {
                        s2.push(s1.pop());
                    }
                }
            } else {
                //数字直接入栈
                s2.push(str);
            }
        }
        //将s1中剩余的运算符依次弹出并压入s2
        while (s1.size() > 0) {
            s2.push(s1.pop());
        }

        return s2;
    }

    public static int calculate(List<String> stringList) {

        Stack<Integer> stack = new Stack<>();

        for (String str : stringList) {
            if (isOpera(str)) {
                int num2 = stack.pop();//第一个出来的是num2
                int num1 = stack.pop();
                int res = cal(num1, num2, str.charAt(0));
                stack.push(res);
            } else if (str.matches("\\d+")) { //如果是数字
                stack.push(Integer.parseInt(str));
            }
        }
        return stack.pop();
    }


    /**
     * @param expression
     * @return
     */
    public static List<String> toInfixExpressionList(String expression) {
        //存放中缀表达式
        List<String> list = new ArrayList<>();
        //多位数拼接字符串
        String str = "";
        //指针
        int index = 0;
        //每遍历到一个字符,就放入c
        char c;
        
        return list;
    }

    //是否为符号
    public static boolean isOpera(String str) {
        return "+-*/".contains(str);
    }

    //计算方法
    public static int cal(int num1, int num2, int oper) {
        int result = 0;
        switch (oper) {
            case '+':
                result = num1 + num2;
                break;
            case '-':
                result = num1 - num2;
                break;
            case '*':
                result = num1 * num2;
                break;
            case '/':
                result = num1 / num2;
                break;
            default:
                break;
        }
        return result;
    }
    //运算符优先级方法
    public static int priority(int oper) {
        if (oper == '*' || oper == '/') {
            return 1;
        } else if (oper == '+' || oper == '-') {
            return 0;
        } else {
            return -1;
        }
    }
}
